# 1146. 快照数组
# 空间复杂度较高，会超时
import bisect


class SnapshotArrayMemoryOver:

    def __init__(self, length: int):
        # 初始化当前的快照
        self.current_snap_id = 0
        # 专门用来存放快照
        self.snap_list = list()
        self.snap_list.append([0] * length)

    def set(self, index: int, val: int) -> None:
        self.snap_list[-1][index] = val

    def snap(self) -> int:
        last_snap_id = self.current_snap_id
        self.current_snap_id += 1
        self.snap_list.append(self.snap_list[-1].copy())
        return last_snap_id

    def get(self, index: int, snap_id: int) -> int:
        if snap_id >= len(self.snap_list):
            return 0
        return self.snap_list[snap_id][index]


# 新接口
class SnapshotArray:

    def __init__(self, length: int):
        # 初始化当前的快照
        self.current_snap_id = 0
        # 初始化数组[[],[],[]]
        self.snap_list = [[] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        self.snap_list[index].append((self.current_snap_id, val))

    def snap(self) -> int:
        last_snap_id = self.current_snap_id
        self.current_snap_id += 1
        return last_snap_id

    def get(self, index: int, snap_id: int) -> int:
        # 确保取的数是最新的那个数，val的值最小是0，所以二分查找传入的 tuple 为 (snap_id + 1, -1)
        # 例：存的是[(0,1),(0,2),(0,3),(1,0),(1,1),(1,2)]
        # 如果snap_id传0，需要返回(0,3)；如果snap_id传1，需要返回(1,2)的下标
        target_index = bisect.bisect_right(self.snap_list[index], (snap_id + 1, -1))
        # 二分查找，右边找的话 target_index 为 len(self.snap_list)，表示没有找到
        return 0 if target_index == 0 else self.snap_list[index][target_index - 1][1]


data = [[0] for _ in range(5)]
print(data)

# Your SnapshotArray object will be instantiated and called as such:
obj = SnapshotArray(3)
obj.set(0, 5)
param_2 = obj.snap()
print(f"param_2:{param_2}")
obj.set(0, 6)
param_3 = obj.get(0, 0)
print(f"param_3:{param_3}")
param_4 = obj.snap()
print(f"param_4:{param_4}")
obj.set(0, 7)
param_5 = obj.get(0, 1)
print(f"param_5:{param_5}")
param_6 = obj.get(0, 2)
print(f"param_6:{param_6}")

obj_2 = SnapshotArray(2)
obj_2.snap()
obj_2.set(1, 17)
obj_2.set(0, 20)
obj_2.snap()
obj_2.snap()
obj_2.snap()

obj_3 = SnapshotArray(1)
obj_3.set(0, 15)
obj_3.snap()
obj_3.snap()
obj_3.snap()
param_1 = obj_3.get(0, 2)
print(f"param_1:{param_1}")

obj_3.snap()
obj_3.snap()
param_2 = obj_3.get(0, 0)
print(f"param_2:{param_2}")
